import "babel-polyfill";
import {enumerate, map, filter} from "../../algorithm/iterator";
import Integer from "../number/integer";
import {gcd as gcdInteger, lcm as lcmInteger, invmod as invmodInteger} from "../number-theory/gcd";
import {generate} from "../number-theory/prime";
import {PolynomialBase} from "./polynomial";
import PolynomialZ, {CannotDivideError} from "./polynomial-Z";
import PolynomialQ from "./polynomial-Q";
import PolynomialZn from "./polynomial-Zn";

export var gcd = function() {
    if (arguments.length === 0) {
        return this.zero;
    }
    if (this === PolynomialZ) {
        var gcd_algorithm = gcdPolynomialZ;
    } else if (this === PolynomialQ) {
        var gcd_algorithm = gcdPolynomialQ;
    } else {
        var gcd_algorithm = this::gcdTemplate;
    }
    var instance = this.instance;
    var result = this.zero;
    for (let polynomial of arguments) {
        result = gcd_algorithm(polynomial, result);
        if (result.degree === 0) {
            return this.one;
        }
    }
    return result;
};

var gcdTemplate = function(p, q) {
    var instance = this.instance;
    p = this.instance.from(p);
    q = this.instance.from(q);
    while (q.degree >= 0) {
        [p, q] = [q, instance.mod(p, q)];
    }
    return p.monic();
};

var gcdPolynomialZ = function(p, q) {
    p = p.primitive();
    q = q.primitive();
    if (p.degree < 0) {
        return q;
    } else if (q.degree < 0) {
        return p;
    } else if (p.degree === 0 || q.degree === 0) {
        return PolynomialZ.one;
    }
    var x = p.leadingCoeff;
    var y = q.leadingCoeff;
    var d = gcdInteger(x, y);
    var e = Integer.multiply(x, Integer.exactDivide(y, d));

    var result = PolynomialZ.zero;
    var product = Integer.one;
    for (let prime of generate()::filter(p => Integer.mod(e, p).sign !== 0)) {
        let PolynomialType = PolynomialZn(prime);
        let instance = PolynomialType.instance;
        let g = PolynomialType::gcdTemplate(p, q);
        if (g.degree === 0) {
            return PolynomialZ.one;
        } else if (g.degree < result.degree || result.degree === -Infinity) {
            product = prime;
            let half_product = Integer.shr(product, 1);
            result = new PolynomialZ(...instance.multiply(g, d)::map(function(n) {
                return Integer.compare(n, half_product) <= 0 ? n : Integer.subtract(n, product);
            }));
        } else if (g.degree === result.degree) {
            let delta = instance.multiply(
                instance.subtract(instance.multiply(g, d), result),
                invmodInteger(product, prime)
            );
            let product_new = Integer.multiply(product, prime);
            let half_product = Integer.shr(product_new, 1);
            let result_old = result;
            result = new PolynomialZ(...result_old::enumerate()::map(function([degree, coeff]) {
                let temp = Integer.add(
                    coeff,
                    Integer.multiply(product, delta.get(degree))
                );
                return Integer.compare(temp, half_product) <= 0 ? temp : Integer.subtract(temp, product_new);
            }));
            if (PolynomialZ.instance.eq(result, result_old)) {
                let temp = result.primitive();
                try {
                    if (PolynomialZ.instance.mod(p, temp).degree === -Infinity
                        && PolynomialZ.instance.mod(q, temp).degree === -Infinity) {
                        return temp;
                    }
                } catch (e) {
                    if (!(e instanceof CannotDivideError)) {
                        throw e;
                    }
                }
            }
            product = product_new;
        }
    }
};

var gcdPolynomialQ = function(p, q) {
    p = PolynomialQ.instance.from(p);
    q = PolynomialQ.instance.from(q);
    var g1 = lcm(...p::map(r => r.denominator));
    p = new PolynomialZ(...p::map(r => Fraction.multiply(r, g1).numerator));
    p = new PolynomialZ(...p::map(r => Integer.exactDivide(
        Integer.multiply(r.numerator, g1),
        r.denominator
    )));
    var g2 = lcm(...p::map(r => r.denominator));
    q = new PolynomialZ(...p::map(r => Integer.exactDivide(
        Integer.multiply(r.numerator, g2),
        r.denominator
    )));
    return new PolynomialQ(gcdInteger(p, q)).monic();
};

export var exGCD = function(p1, p2) {
    var instance = this.instance;
    p1 = instance.from(p1);
    p2 = instance.from(p2);
    var [a1, a2, b1, b2] = [this.zero, this.one, this.one, this.zero];
    while (p1.degree >= 0) {
        let q;
        [[q, p1], p2] = [instance.divmod(p2, p1), p1];
        [a1, a2] = [a2, instance.subtract(a1, instance.multiply(q, a2))];
        [b1, b2] = [b2, instance.subtract(b1, instance.multiply(q, b2))];
    }
    if (p2.degree >= 0) {
        let leading_coeff = p2.leadingCoeff;
        p2 = instance.divide(p2, leading_coeff);
        a1 = instance.divide(a1, leading_coeff);
        b1 = instance.divide(b1, leading_coeff);
    }
    return [p2, a1, b1];
};

export var invmod = function(p, q) {
    return this::exGCD(p, q)[1];
};
